/*
 * @Author: szx
 * @Date: 2022-03-13 17:19:23
 * @LastEditTime: 2022-03-13 18:23:04
 * @Description:
 * @FilePath: \leetcode\other\银联-03. 理财产品\03.cpp
 */
#include <iostream>
#include <queue>
#include <unordered_map>
#include <vector>
using namespace std;
class Solution {
   public:
    //大顶堆
    class mycomparison {
       public:
        bool operator()(const pair<long long, long long>& lhs,
                        const pair<long long, long long>& rhs) {
            return lhs.first < rhs.first;
        }
    };
    int maxInvestment(vector<int>& product, int limit) {
        unordered_map<long long, long long> map;
        sort(product.begin(), product.end()) int l = 0;
        for (long long i : product) {
            if (l < limit) {
                map[i]++;
            }
        }
        priority_queue<pair<long long, long long>,
                       vector<pair<long long, long long>>, mycomparison>
            pri_que;

        for (auto it = map.begin(); it != map.end(); it++) {
            pri_que.push(*it);
        }
        long long mod = 1e9 + 7;

        long long res = 0;
        long long last = 0;
        while (limit > 0 && pri_que.size() != 0) {
            auto tmp = pri_que.top();
            if (tmp.second + last < limit) {
                long long sum = tmp.first * (tmp.second + last);
                sum = sum % mod;
                res = (sum + res) % mod;
                limit -= tmp.second + last;
            } else {
                long long sum = tmp.first * limit;
                sum = sum % mod;
                res = (sum + res) % mod;
                return res;
            }
            pri_que.pop();
            if (tmp.first - 1 > 0) {
                if (pri_que.top().first == tmp.first - 1) {
                    last += tmp.second;
                } else {
                    if (pri_que.size() != 0) {
                        pri_que.push(
                            make_pair(tmp.first - 1, tmp.second + last));
                        last = 0;
                    } else {
                    }
                }
            }
        }
        // cout<<limit<<endl;
        return res;
    }
};